package SwordForOffer.Problem38;

import java.util.Arrays;

public class GetNumberOfK {
	/*
	 * 统计一个数字在排序数组中出现的次数
	 */
	public int getNumberOfK(int[] arraySorted,int k)
	{
		int result=0;
		if(arraySorted==null)
			return 0;

		if(arraySorted.length==1)
		{
			if(arraySorted[0]==k)
				return 1;
			else
				return 0;
		}

		if(k < arraySorted[arraySorted.length/2])
			result+=getNumberOfK(Arrays.copyOfRange(arraySorted, 0, arraySorted.length/2),k);
		else
			if(k>arraySorted[arraySorted.length/2])
				 result+=getNumberOfK(Arrays.copyOfRange(arraySorted, arraySorted.length/2, arraySorted.length),k);
			else {
				 result+=getCount(arraySorted, arraySorted.length/2);
			}
		return result;
	}
	private int getCount(int[] arraySorted,int index) {
		int k=arraySorted[index];
		int result=0;

		for(int i=index;i<arraySorted.length;i++) {
			if(arraySorted[i]==k)
				result++;
			else 
				break;
		}
		for(int i=index-1;i>=0;i--) {
			if(arraySorted[i]==k)
				result++;
			else 
				break;
		}
		return result;		
	}

	public int myGetNumberOfK(int[] array, int k) {
		if (array == null || array.length < 1){
			return 0;
		}
		int findIndexK = myFindIndex(array,0,array.length - 1,k,0);
		int findStartIndexK;
		int findEndIndexK;
		if (findIndexK > 0){
			findStartIndexK = myFindIndex(array,0,array.length - 1,k,-1);
			findEndIndexK = myFindIndex(array,0,array.length - 1,k,1);
		}else {
			return findIndexK;
		}
		return findEndIndexK - findStartIndexK + 1;
	}

	private int myFindIndex(int[] array, int start, int end, int k, int direction) {
		if (end - start < 0){
			return 0;
		}
		if (end - start == 0){
			if (array[start] == k){
				return start;
			}else {
				return 0;
			}
		}
		int center = (end + start) / 2;
		if (direction == 0){
			if (array[center] == k){
				return center;
			}else {
				if (array[center] < k){
					return myFindIndex(array,center,end,k,direction);
				}else{
					return myFindIndex(array,start,center,k,direction);
				}
			}
		}else {
			if (array[center] == k){
				if (array[center + direction] != k ){
					return center;
				}else {
					if (direction > 0){
						return myFindIndex(array,center,end,k,direction);
					}else {
						return myFindIndex(array,start,center,k,direction);
					}
				}
			}else {
				if (array[center] < k){
					return myFindIndex(array,center,end,k,direction);
				}else{
					return myFindIndex(array,start,center,k,direction);
				}
			}
		}
	}
}
